package algorithm;

public class LeetCode91 {
    public static int numDecodings(String s) {
        if (s.length() < 1 || s.charAt(0) == '0'){
            return 0;
        }

        return dfs(0, s);

    }

    private static int dfs(int i, String s) {
        if (i >= s.length()) {
            return 1;
        }

        int ans = 0;
        if (i + 2 <= s.length()) {
            int num = Integer.parseInt(s.substring(i, i + 2));
            if (num >= 10 && num <= 26) {
                ans += dfs(i+2, s);
            }
        }
        if (s.charAt(i) != '0'){
            ans += dfs(i+1, s);
        }
        return ans;
    }

    private static int dfs2(int i, String s) {
        if (i >= s.length()) {
            return 1;
        }

        int ans = 0;
        if (i + 2 <= s.length() && s.substring(i+1).equals("0")) {
            ans += dfs2(i+2, s);
        } else if (i + 2 <= s.length())  {
            ans += dfs2(i+2, s);
            ans += dfs(i+1, s);
        } else {
            ans += dfs(i+1,s);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.printf(numDecodings("1111") + "");
    }
}
